package 面试题36_二叉搜索树与双向链表;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 17:05 2021/3/14
 * @Description：
 */
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

public class Solution {
    // 用于标记已经转换好的双向链表的头部和尾部
    Node head = null;
    Node tail = null;

    public Node treeToDoublyList(Node root) {

        if (root == null) return null;

        convertRecur(root);
        // 最后将头节点指向尾节点，尾节点指向头节点，实现循环双向链表
        head.left = tail;
        tail.right = head;

        return head;
    }

    void convertRecur(Node curNode) {
        if (curNode == null) {
            return;
        }

        convertRecur(curNode.left);

        if (tail == null) {
            // 还未开始转换，则当前节点就是要返回的双向链表的头节点
            head = curNode;
        } else {
            // 否则，将当前节点和已经转换好的链表进行连接
            // 链表的尾节点右指针指向当前节点
            // 当前节点的左指针指向链表的尾节点
            tail.right = curNode;
            curNode.left = tail;
        }

        // 将当前节点作为链表的尾节点
        tail = curNode;

        // 转换右子树
        convertRecur(curNode.right);
    }
}
